import java.util.*;
import java.io.*;

public class BinaryHeap<AnyType extends Comparable<? super AnyType>> extends AbstractQueue<AnyType>
{
    private static final int DEFAULT_CAPACITY = 100;
    private static int currentSize;      // Nombre d'elements
    private AnyType [ ] array;    // Tableau contenant les donnees (premier element a l'indice 1)
    private boolean min;
    private int modifications;    // Nombre de modifications apportees a ce monceau
    
    @SuppressWarnings("unchecked")
    public BinaryHeap( boolean min )
    {
	this.min = min;
	currentSize = 0;
	array = (AnyType[]) new Comparable[ DEFAULT_CAPACITY + 1];
    }
    
    @SuppressWarnings("unchecked")
    public BinaryHeap( AnyType[] items, boolean min )
    {
	this.min = min;
	this.array =  (AnyType[]) new Comparable[ items.length + 1];
	this.array[0] = null;
	for(int i=1; i <= items.length; i++){
		array[i] = items[i-1];
	}
 
	// COMPLETEZ
	// invoquez buildMinHeap() ou buildMaxHeap() en fonction du parametre min;
	this.currentSize = items.length;
	
	if(min)
	{buildMinHeap();}
	else
		buildMaxHeap();
    }
    
    public boolean offer( AnyType x )
    {
	if (x == null)
	    throw new NullPointerException("Cannot insert null in a BinaryHeap");
	
	if( currentSize + 1 == array.length )
	    doubleArray();
	
	// COMPLETEZ
	int hole = ++currentSize;
	
	if(min){
		for ( ; hole > 1 && x.compareTo( array[ hole/2 ]) < 0; hole /= 2)
			array[ hole ] = array[ hole / 2 ] ;
		array[ hole ] = x;
	}
	else {
		for ( ; hole > 1 && array[ hole/2 ].compareTo(x) < 0; hole /= 2)
			array[ hole ] = array[ hole / 2 ] ;
		array[ hole ] = x;
	}
	return true;
    }
    
    public AnyType peek()
    {
	if(!isEmpty())
	    return array[1];
	
	return null;
    }
    
    public AnyType poll() 
    {
    	//COMPLETEZ
    	if( isEmpty( ) )
			try {
				throw new Exception();
			} catch (Exception e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}

    	
    	array[ 1 ] = array[ currentSize-- ]; 
    	if(min)
    		percolateDownMinHeap(1, currentSize);
    	else
    		percolateDownMaxHeap(1, currentSize);
    	
    	return array[1];

	
    }
    
    public Iterator<AnyType> iterator()
    {
	return new HeapIterator();
    }
    
    private void buildMinHeap()
    {
	//COMPLETEZ
    	for (int i=currentSize/2;i>0;i--)
    		percolateDownMinHeap( i, currentSize);
    }
    
    private void buildMaxHeap()
    {
	//COMPLETEZ
    	for (int i=currentSize/2;i>0;i--)
    		percolateDownMaxHeap( i, currentSize);
    }
    
    public boolean isEmpty()
    {
	return currentSize == 0;
    }
    
    public int size()
    {
	return currentSize;
    }
    
    public void clear()
    {
	currentSize = 0;
	modifications = 0;
	array = (AnyType[]) new Comparable[ DEFAULT_CAPACITY + 1];
    }
    
    private static int leftChild( int i, boolean heapIndexing )
    {
	return ( heapIndexing ? 2*i : 2*i+1 );
    }
    
    private void swapReferences( int index1, int index2 )
    {
	swapReferences(array, index1, index2);
    }
    
    private static <AnyType extends Comparable<? super AnyType>>
				    void swapReferences( AnyType[] array, int index1, int index2 )
    {
	AnyType tmp = array[ index1 ];
	array[ index1 ] = array[ index2 ];
	array[ index2 ] = tmp;
    }
    
    @SuppressWarnings("unchecked")
	private void doubleArray()
    {
	AnyType [ ] newArray;
	
	newArray = (AnyType []) new Comparable[ array.length * 2 ];
	for( int i = 0; i < array.length; i++ )
	    newArray[ i ] = array[ i ];
	array = newArray;
    }
    
    
    /**
     * @param hole    Position a percoler
     * @param size    Indice max du tableau
     */
    private void percolateDownMinHeap( int hole, int size )
    {
	percolateDownMinHeap(array, hole, size, true);
    }
    
    /**
     * @param array   Tableau d'element
     * @param hole    Position a percoler
     * @param size    Indice max du tableau
     * @param heapIndexing  True si les elements commencent a l'index 1, false sinon
     */
    private static <AnyType extends Comparable<? super AnyType>>
				    void percolateDownMinHeap( AnyType[] array, int hole, int size, boolean heapIndexing )
    {
	//COMPLETEZ
    	int child=0;
    	AnyType temp = array[hole];
    	
    	for(;hole*2 <= size; hole=child)
    	{
    		if (heapIndexing)
    			child = hole*2;
    		else
    			child = hole*2+1;
    		
    		if (child!=size && array[child+1].compareTo(array[child])<0)
    			child ++;//on considÃ‹re le fils de droite
    		
    		if(array[child].compareTo(temp)<0)
    			array[hole] = array[child];
    		else
    			break;
    	}
    	array[hole]=temp;//on rÃˆinsÃ‹re l'ÃˆlÃˆment de dÃˆpart
    }
    
    /**
     * @param hole    Position a percoler
     * @param size    Indice max du tableau
     */
    private void percolateDownMaxHeap( int hole, int size )
    {
	percolateDownMaxHeap(array, hole, size, true);
    }
    
    /**
     * @param array         Tableau d'element
     * @param hole          Position a percoler
     * @param size          Indice max du tableau
     * @param heapIndexing  True si les elements commencent a l'index 1, false sinon
     */
    private static <AnyType extends Comparable<? super AnyType>> 
				    void percolateDownMaxHeap( AnyType[] array, int hole, int size, boolean heapIndexing )
    {
	//COMPLETEZ
    	int child=0;
    	AnyType temp = array[hole];
    	
    	for(;hole*2 <= size; hole=child)
    	{
    		if (heapIndexing)
    			child = hole*2;
    		else
    			child = hole*2+1;
    		
    		if (child!=size && array[child+1].compareTo(array[child])>0)
    			child ++;//on considÃ‹re le fils de droite
    		
    		if(array[child].compareTo(temp)>0)
    			array[hole] = array[child];
    		else
    			break;
    	}
    	array[hole]=temp;//on rÃˆinsÃ‹re l'ÃˆlÃˆment de dÃˆpart
    }
    
    public static <AnyType extends Comparable<? super AnyType>>
				   void heapSort( AnyType[] a )
    {
	//COMPLETE
    	for( int i = a.length / 2; i >= 0; i-- ) /* construire le monceau */ 
    		percolateDownMaxHeap( a, i, a.length-1,true );
    	for( int i = a.length - 1; i > 0; i-- ) {
    		swapReferences( a, 0, i ); /* permuter le maximum (racine) avec le dernieÌ€re eÌ�leÌ�ment du monceau */
    		percolateDownMaxHeap( a, 0, i-1, true );
    	     }
    }
    
    public static <AnyType extends Comparable<? super AnyType>>
				   void heapSortReverse( AnyType[] a )
    {
	//COMPLETEZ
    	for( int i = a.length / 2; i >= 0; i-- ) /* construire le monceau */ 
    		percolateDownMinHeap( a, i, a.length-1,true );
    	for( int i = a.length - 1; i > 0; i-- ) {
    		swapReferences( a, 0, i ); /* permuter le maximum (racine) avec le dernieÌ€re eÌ�leÌ�ment du monceau */
    		percolateDownMinHeap( a, 0, i-1, true );
    	     }
    }
    
    public String nonRecursivePrintFancyTree()
    {
	String outputString = "";
	
	//COMPLETEZ
/*	int j=1;
	boolean issonleft=true;
	for (int i=1;i<=currentSize;i++)
		{j = 1;
		if (i==1)//on affiche la racine
			outputString+="|__"+array[1];
		else
			{
			outputString+="   ";
			if (i<currentSize/2)
				outputString+="|";
			}
		outputString+="\n";
		if (i%2==0)
			issonleft=true;
		else
			issonleft=false;
		}
	*/
	
	int index = 1;
	boolean isLeaf;
	int counter = 0;
	do{
		
		isLeaf = index > currentSize/2;
		
		while(!isLeaf){
			isLeaf = index > currentSize/2;
			for(int i=0; i<counter; i++)
				outputString += "   ";
			outputString += "|__" + array[index] + "\n";
			index *= 2;
			counter++;
			
			}
			index /= 2;
			index++;
			if( index <= currentSize ){
				for(int i=0; i<counter-1; i++)
					outputString += "   ";
				outputString += "|__" + array[index] + "\n";
			}
				
			else{
				for(int i=0; i<counter-1; i++)
					outputString += "   ";
				outputString += "|__" + "null\n";
			}
			do{
			index = ((index-1)/2);
			counter--;
			}while((index) % 2 == 1);
			index++;
			counter--;
	} while(index > 2);
	
	return outputString;
    }
    
    public String printFancyTree()
    {
	return printFancyTree(1, "");
    }
    
    private String printFancyTree( int index, String prefix)
    {
	String outputString = "";
	
	outputString = prefix + "|__";
	
	if( index <= currentSize )
	    {
		boolean isLeaf = index > currentSize/2;
		
		outputString += array[ index ] + "\n";
		
		String _prefix = prefix;
		
		if( index%2 == 0 )
		    _prefix += "|  "; // un | et trois espace
		else
		    _prefix += "   " ; // quatre espaces
		
		if( !isLeaf ) {
		    outputString += printFancyTree( 2*index, _prefix);
		    outputString += printFancyTree( 2*index + 1, _prefix);
		}
	    }
	else
	    outputString += "null\n";
	
	return outputString;
    }
    
    private class HeapIterator implements Iterator {
	
	public boolean hasNext() {
		
	    //COMPLETEZ
		return min;
	}

	public Object next() throws NoSuchElementException, 
				    ConcurrentModificationException, 
				    UnsupportedOperationException {
	    //COMPLETEZ
		
		
		return array;
	}
	
	public void remove() {
	    throw new UnsupportedOperationException();
	}
    }
}
